


package main

import (
    "fmt";
    "graph";
)




func makeGraph() (*graph.Graph) {
    g := graph.NewGraph(false);
    
    g.AddEdgeWithWeight(1, 2, 3);
    g.AddEdgeWithWeight(1, 3, 6);
    g.AddEdgeWithWeight(1, 10, 9);
    g.AddEdgeWithWeight(2, 3, 4);
    g.AddEdgeWithWeight(2, 4, 2);
    g.AddEdgeWithWeight(2, 9, 9);
    g.AddEdgeWithWeight(2, 10, 9);
    g.AddEdgeWithWeight(3, 4, 2);
    g.AddEdgeWithWeight(3, 5, 9);
    g.AddEdgeWithWeight(4, 5, 9);
    g.AddEdgeWithWeight(4, 9, 8);
    g.AddEdgeWithWeight(5, 6, 4);
    g.AddEdgeWithWeight(5, 7, 5);
    g.AddEdgeWithWeight(5, 9, 7);
    g.AddEdgeWithWeight(6, 7, 1);
    g.AddEdgeWithWeight(6, 8, 4);
    g.AddEdgeWithWeight(7, 8, 3);
    g.AddEdgeWithWeight(7, 9, 9);
    g.AddEdgeWithWeight(8, 9, 10);
    g.AddEdgeWithWeight(8, 10, 18);
    g.AddEdgeWithWeight(9, 8, 10);
    g.AddEdgeWithWeight(9, 10, 8);
    return g;
}

// The graph from example at http://scienceblogs.com/goodmath/2007/08/shortest_paths_and_greedy_rela_1.php
func makeGoodMathShortestPathExample() (*graph.Graph) {
     g := graph.NewGraph(false);
     
     g.AddEdgeWithWeight("A", "B", 3);
     g.AddEdgeWithWeight("A", "D", 5);
     g.AddEdgeWithWeight("B", "E", 11);
     g.AddEdgeWithWeight("D", "C", 7);
     g.AddEdgeWithWeight("D", "F", 8);
     g.AddEdgeWithWeight("C", "F", 2);
     g.AddEdgeWithWeight("E", "H", 4);
     g.AddEdgeWithWeight("F", "H", 6);
     g.AddEdgeWithWeight("F", "G", 1);
     g.AddEdgeWithWeight("E", "I", 3);
     g.AddEdgeWithWeight("H", "I", 2);
     g.AddEdgeWithWeight("I", "L", 13);
     g.AddEdgeWithWeight("H", "L", 6);
     g.AddEdgeWithWeight("L", "M", 5);
     g.AddEdgeWithWeight("L", "K", 2);
     g.AddEdgeWithWeight("M", "K", 1);
     g.AddEdgeWithWeight("H", "J", 4);
     g.AddEdgeWithWeight("J", "K", 7);
     g.AddEdgeWithWeight("G", "J", 4);
     return g;
}


func makeGraphWithNegativeCycle() (*graph.Graph) {
    g := graph.NewGraph(true);
    
    g.AddEdgeWithWeight("a", "b", 6);
    g.AddEdgeWithWeight("a", "c", 7);
    g.AddEdgeWithWeight("b", "c", 2);
    g.AddEdgeWithWeight("b", "e", -4);
    g.AddEdgeWithWeight("c", "e", 9);
    g.AddEdgeWithWeight("c", "d", -3);
    g.AddEdgeWithWeight("e", "a", 2);
    g.AddEdgeWithWeight("e", "d", 7);
    g.AddEdgeWithWeight("d", "b", -2);
    return g;
}


func makeGraphWithNegativeWeights() (*graph.Graph) {
    g := graph.NewGraph(true);
    
    g.AddEdgeWithWeight("s", "t", 6);
    g.AddEdgeWithWeight("s", "y", 7);
    g.AddEdgeWithWeight("t", "x", 5);
    g.AddEdgeWithWeight("x", "t", -2);
    g.AddEdgeWithWeight("t", "z", -4);
    g.AddEdgeWithWeight("y", "x", -3);
    g.AddEdgeWithWeight("y", "z", 9);
    g.AddEdgeWithWeight("z", "x", 7);
    g.AddEdgeWithWeight("z", "s", 2);
    return g;
}



func main() {
    g1 := makeGraph();
    pred, cost := graph.MinTreePrim(g1, 1);
        
    for child, parent := range pred {
        fmt.Printf("%d -> %d\n", child, parent);
    }
    fmt.Printf("Total cost = %d\n\n", cost);
    
    edges, cost := graph.MinTreeKruskal(g1);
    fmt.Printf("Min Tree: %s\n", edges);
    fmt.Printf("Total cost = %d\n\n", cost);
    
    
    
    
    
    g2 := makeGoodMathShortestPathExample();
    distMap, predMap := graph.ShortestPathDijkstra(g2, "A");
    
    dist, path := graph.ExtractPath("A", "M", distMap, predMap);
    fmt.Printf("%s\n", distMap);
    fmt.Printf("%s\n", predMap);
    fmt.Printf("Distance = %d\n", dist);
    fmt.Printf("Path = %s\n", path);
    
    
    // g3 := makeGraphWithNegativeWeights();
    g3 := makeGoodMathShortestPathExample();
    distMap, predMap = graph.ShortestPathBellmanFord(g3, "A");
    
    if distMap == nil {
        fmt.Printf("Cycle!!\n");
    } else {
        fmt.Printf("%s\n", distMap);
        fmt.Printf("%s\n", predMap);
        dist, path := graph.ExtractPath("A", "M", distMap, predMap);    
        fmt.Printf("Distance = %d\n", dist);
        fmt.Printf("Path = %s\n", path);
    }
    
}